The present invention relates to computer graphics, geometry processing, image processing, computer vision and pattern recognition, and more particularly, but not exclusively, to approximation of distance maps used in applications therein.
Distance maps are often used for approximation of geodesic distances on manifolds, where manifold refers to an n-dimensional space with given local metric properties. Examples of manifold include images, curved surfaces, three-dimensional volumes (say, in computer games, or for collision detection, as known in the art), etc.
Approximation of geodesic distances on manifolds is an important computational geometry problem, appearing in many applications in the fields of computer graphics, geometry processing, image processing, computer vision and pattern recognition.
Examples include: Surface segmentation and editing methods which are based on cutting the surface along geodesic paths, Parameterization and texture mapping, Collision detection, Correspondence and matching, Shape classification, Mesh Deformation and Editing, Farthest point sampling, Path planning and navigation.
As known in the art, the problem of distance map approximation may be formulated as the viscosity solution of the eikonal equation. Eikonal equation governs the behavior of wavefront propagation from the source point through a medium with given properties. The solution of the eikonal equation demonstrates that the wavefront traverse the path between two points, which takes the least time, which is equivalent to choosing the shortest path available between the two points.
A widely used method for approximation of distance is known as Fast Marching.
The main idea of the fast marching method is to simulate a wave front advancing from a set of source points positioned in a Euclidean grid applied on a discrete representation of a manifold.
The propagating front may be thought of as a “prairie fire” evolution towards directions where the grid is not yet “burnt out”. At time t=0, the fire starts at the source points, and the Fast Marching method's update scheme is used to compute the time values t for each grid point the advancing “fire front” reaches, as described in further detail hereinbelow.
For finding the shortest paths in a manifold, Fast Marching maintains a set of fixed grid points, for which the time of arrival is already known, and a priority queue of all other grid points sorted by their times of wave front arrival.
Reference is now made to FIG. 1, which illustrates an update step, according to prior art.
The basic operation of the fast marching method is the update step, using the Fast Marching update scheme. The Fast Marching update scheme is used to calculate the time of arrival of the wave front to a first grid point (x0) based on the previously calculated times of arrival of the wave front to grid points (x1, x2) immediately adjacent to the first grid points (x0), which comprises the distance value for the grid point (x0).
As illustrated using FIG. 1, fast marching method's original update scheme is based on simulating a planar wave front propagating inside the triangle. Distance values of two supporting grid points (x1, x2) on the grid allow approximation of the front direction.
Currently, the fast marching method is also generalized to arbitrary triangulated surfaces, unstructured meshes, implicit unorganized surfaces, and parametric surfaces.